{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Append Characters to String to Make Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: appendCharacters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #追加字符以获得子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你两个仅由小写英文字母组成的字符串 <code>s</code> 和 <code>t</code> 。</p>\n",
    "\n",
    "<p>现在需要通过向 <code>s</code> 末尾追加字符的方式使 <code>t</code> 变成 <code>s</code> 的一个 <strong>子序列</strong> ，返回需要追加的最少字符数。</p>\n",
    "\n",
    "<p>子序列是一个可以由其他字符串删除部分（或不删除）字符但不改变剩下字符顺序得到的字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"coaching\", t = \"coding\"\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>向 s 末尾追加字符串 \"ding\" ，s = \"coachingding\" 。\n",
    "现在，t 是 s (\"<em><strong>co</strong></em>aching<em><strong>ding</strong></em>\") 的一个子序列。\n",
    "可以证明向 s 末尾追加任何 3 个字符都无法使 t 成为 s 的一个子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abcde\", t = \"a\"\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>t 已经是 s (\"<em><strong>a</strong></em>bcde\") 的一个子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"z\", t = \"abcde\"\n",
    "<strong>输出：</strong>5\n",
    "<strong>解释：</strong>向 s 末尾追加字符串 \"abcde\" ，s = \"zabcde\" 。\n",
    "现在，t 是 s (\"z<em><strong>abcde</strong></em>\") 的一个子序列。 \n",
    "可以证明向 s 末尾追加任何 4 个字符都无法使 t 成为 s 的一个子序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, t.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>s</code> 和 <code>t</code> 仅由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [append-characters-to-string-to-make-subsequence](https://leetcode.cn/problems/append-characters-to-string-to-make-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [append-characters-to-string-to-make-subsequence](https://leetcode.cn/problems/append-characters-to-string-to-make-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"coaching\"\\n\"coding\"', '\"abcde\"\\n\"a\"', '\"z\"\\n\"abcde\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        j = 0\n",
    "        for ch in s:\n",
    "            if ch == t[j]:\n",
    "                j += 1\n",
    "            if j == len(t):\n",
    "                return 0\n",
    "        return len(t) - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0, len(s)\n",
    "        for j, c in enumerate(t):\n",
    "            while i < n and s[i] != t[j]: i += 1\n",
    "            if i == n: return len(t) - j\n",
    "            i += 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i=j=0\n",
    "        ii=len(s)\n",
    "        jj=len(t)\n",
    "        while i<ii:\n",
    "            if s[i]==t[j]:\n",
    "                j+=1\n",
    "                if j==jj:return 0 \n",
    "            i+=1\n",
    "            \n",
    "        return jj-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i=j=0\n",
    "        ii=len(s)\n",
    "        jj=len(t)\n",
    "        while i<ii:\n",
    "            if s[i]==t[j]:\n",
    "                j+=1\n",
    "            i+=1\n",
    "            if j==jj:return 0 \n",
    "        return jj-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        \n",
    "        lt = len(t)\n",
    "        ls = len(s)\n",
    "        i = j = 0\n",
    "        while i<ls and j<lt:\n",
    "            while i<ls and s[i]!=t[j]:\n",
    "                i+=1\n",
    "            if i==ls:\n",
    "                break\n",
    "            j+=1\n",
    "            i+=1\n",
    "        return lt-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        # 表示t中第j个字符在s中匹配第i个字符\n",
    "        i,j = 0,0\n",
    "        m,n = len(s),len(t)\n",
    "        while i < m and j < n:\n",
    "            if s[i] != t[j]:\n",
    "                i += 1\n",
    "            else:\n",
    "                i += 1\n",
    "                j += 1\n",
    "        return n - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        j, m = 0, len(t)\n",
    "        for c in s:\n",
    "            if c == t[j]:\n",
    "                j += 1\n",
    "                if j == m:\n",
    "                    return 0\n",
    "        return m - j\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(s)\n",
    "        # n = len(t)\n",
    "        # p1 = p2 = 0\n",
    "        # while p1 < m and p2 < n:\n",
    "        #     if s[p1] == t[p2]:\n",
    "        #         p1 += 1\n",
    "        #         p2 += 1\n",
    "        #     else:\n",
    "        #         p1 += 1\n",
    "        \n",
    "        # return n - p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(s) and j < len(t):\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        if i == len(s): return len(t) - j\n",
    "        else: return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i = j = 0\n",
    "        while i < len(s) and j < len(t):\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return len(t) - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        i = 0\n",
    "        for j in range(n):\n",
    "            while i < m and s[i] != t[j]:\n",
    "                i += 1\n",
    "            if i == m:\n",
    "                return n - j\n",
    "            i += 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        left = 0\n",
    "        right = len(t)\n",
    "\n",
    "        def check(tar):\n",
    "            ss = t\n",
    "\n",
    "            i = 0\n",
    "            j = 0\n",
    "\n",
    "            while i < tar and j < len(s):\n",
    "                if ss[i] != s[j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            \n",
    "            return i == tar\n",
    "            \n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return len(t) - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        idx=0\n",
    "        for i in range(len(s)):\n",
    "            if idx==len(t):\n",
    "                return 0\n",
    "            if s[i]==t[idx]:\n",
    "                idx+=1\n",
    "        return len(t)-idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i = j = 0\n",
    "        while j<len(t) and i<len(s):\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return len(t) - j\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        j, m = 0, len(t)\n",
    "        for c in s:\n",
    "            if c == t[j]:\n",
    "                j += 1\n",
    "                if j == m:\n",
    "                    return 0\n",
    "        return m - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0,len(s)\n",
    "        for j,c in enumerate(t):\n",
    "            while i < n and s[i] != t[j]:\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                return len(t) - j\n",
    "            i += 1\n",
    "        return 0\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # j, m = 0, len(t)\n",
    "        # for c in s:\n",
    "        #     if c == t[j]:\n",
    "        #         j += 1\n",
    "        #         if j == m:\n",
    "        #             return 0\n",
    "        # return m - j\n",
    "\n",
    "\n",
    "\n",
    "        # m = len(s)\n",
    "        # n = len(t)\n",
    "        # p1 = p2 = 0\n",
    "        # while p1 < m and p2 < n:\n",
    "        #     if s[p1] == t[p2]:\n",
    "        #         p1 += 1\n",
    "        #         p2 += 1\n",
    "        #     else:\n",
    "        #         p1 += 1\n",
    "        \n",
    "        # return n - p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        m = len(s)\n",
    "        n = len(t)\n",
    "        p1 = p2 = 0\n",
    "        while p1 < m and p2 < n:\n",
    "            if s[p1] == t[p2]:\n",
    "                p1 += 1\n",
    "                p2 += 1\n",
    "            else:\n",
    "                p1 += 1\n",
    "        \n",
    "        return n - p2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < len(s) and j < len(t):\n",
    "            if s[i] == t[j]:\n",
    "                j += 1\n",
    "\n",
    "            i += 1\n",
    "        return len(t)-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        it = iter(t)\n",
    "        wc = next(it)\n",
    "        for c in s:\n",
    "            if c == wc:\n",
    "                wc = next(it, None)\n",
    "                if wc is None: return 0\n",
    "        return sum(1 for _ in it) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i = j = 0\n",
    "        ls = len(s)\n",
    "        lt = len(t)\n",
    "        while i < ls and j < lt:\n",
    "            while i < ls and s[i] != t[j]:\n",
    "                i += 1\n",
    "            if i >= ls:\n",
    "                break\n",
    "            j += 1\n",
    "            i += 1\n",
    "        return lt - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0, len(s)\n",
    "        for j, c in enumerate(t):\n",
    "            while i < n and s[i] != t[j]: i += 1\n",
    "            if i == n: return len(t) - j\n",
    "            i += 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, j = 0, 0\n",
    "        while i < len(s) and j < len(t):\n",
    "            if s[i] == t[j]:\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return len(t)-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        j = 0\n",
    "        for i, c in enumerate(s):\n",
    "            if j == len(t): break\n",
    "            if j < len(t) and c == t[j]:\n",
    "                j += 1\n",
    "                continue\n",
    "        return len(t) - j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i = j = 0\n",
    "        while j<len(t) and i<len(s):\n",
    "            if s[i] == t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        ans = len(t) - j\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i=j=0\n",
    "        ii=len(s)\n",
    "        jj=len(t)\n",
    "        while i<ii:\n",
    "            if s[i]==t[j]:\n",
    "                j+=1\n",
    "            i+=1\n",
    "            if j==jj:return 0 \n",
    "        return jj-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        poss = 0 \n",
    "        post = 0\n",
    "        while post < len(t) and poss < len(s):\n",
    "            if s[poss] == t[post]:\n",
    "                post += 1\n",
    "            poss += 1\n",
    "        return len(t) - post"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        left = 0\n",
    "        for i in range(m):\n",
    "            if(s[i] == t[left]):\n",
    "                left += 1\n",
    "            if(left == n):\n",
    "                return 0\n",
    "        return n - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0, len(s)\n",
    "        for j, c in enumerate(t):\n",
    "            while i < n and s[i] !=t[j]:\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                return len(t) - j\n",
    "            i += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        ans=0\n",
    "        for i in s:\n",
    "            if ans==len(t):return 0\n",
    "            if i==t[ans]:ans+=1\n",
    "        return len(t)-ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        left = 0\n",
    "        for i in range(m):\n",
    "            if(s[i] == t[left]):\n",
    "                left += 1\n",
    "            if(left == n):\n",
    "                return 0\n",
    "        return n - left\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        n = len(t)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for w in s:\n",
    "            if i < n and t[i] == w:\n",
    "                i += 1\n",
    "        return n-i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i = j = 0\n",
    "        while i<len(s) and j<len(t):\n",
    "            if s[i]== t[j]:\n",
    "                i += 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return len(t)-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0, len(s)\n",
    "        for j, c in enumerate(t):\n",
    "            while i < n and s[i] != t[j]: i += 1\n",
    "            if i == n: return len(t) - j\n",
    "            i += 1\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        m, n = len(s), len(t)\n",
    "        j = 0\n",
    "        for i in range(m):\n",
    "            if j >= n:\n",
    "                break\n",
    "            if s[i] == t[j]:\n",
    "                j += 1\n",
    "                # print(i,j)\n",
    "\n",
    "        return n-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        n = len(t)\n",
    "        指针 = 0\n",
    "        for i in s:\n",
    "            if 指针 == n:\n",
    "                return 0\n",
    "            else:\n",
    "                if t[指针] == i:\n",
    "                    指针 += 1\n",
    "        return n - 指针"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0, len(s)\n",
    "        for j, c in enumerate(t):\n",
    "            while i < n and s[i] != t[j]: i += 1\n",
    "            if i == n: return len(t) - j\n",
    "            i += 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        left = 0\n",
    "        right = len(t)\n",
    "\n",
    "        def check(tar):\n",
    "            ss = t[:tar]\n",
    "\n",
    "            i = 0\n",
    "            j = 0\n",
    "\n",
    "            while i < len(ss) and j < len(s):\n",
    "                if ss[i] != s[j]:\n",
    "                    j += 1\n",
    "                else:\n",
    "                    i += 1\n",
    "                    j += 1\n",
    "            \n",
    "            return i == len(ss)\n",
    "            \n",
    "\n",
    "        while left < right:\n",
    "            mid = left + (right - left + 1) // 2\n",
    "\n",
    "            if check(mid):\n",
    "                left = mid\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return len(t) - left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        n=len(t)\n",
    "        j=0\n",
    "        for i in range(len(s)):\n",
    "            if t[j]==s[i]:\n",
    "                j+=1\n",
    "                if j==n:\n",
    "                    return 0\n",
    "        return n-j\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        j=0\n",
    "        jj=len(t)\n",
    "        for c in s:\n",
    "            if c==t[j]:\n",
    "                j+=1\n",
    "                if j==jj:return 0\n",
    "        return jj-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        s_len, t_len = len(s), len(t)\n",
    "        s_ptr, t_ptr = 0, 0\n",
    "        while s_ptr < s_len and t_ptr < t_len:\n",
    "            if s[s_ptr] == t[t_ptr]:\n",
    "                t_ptr += 1\n",
    "            s_ptr += 1\n",
    "        return t_len - t_ptr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0, len(s)\n",
    "        for j, c in enumerate(t):\n",
    "            while i < n and s[i] != t[j]: i += 1\n",
    "            if i == n: return len(t) - j\n",
    "            i += 1\n",
    "        return 0\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i,j=0,0\n",
    "        while i<len(s) and j<len(t):\n",
    "            if s[i]==t[j]:\n",
    "                i+=1\n",
    "                j+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        return len(t)-j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        idx=0\n",
    "        for i in range(len(s)):\n",
    "            if idx==len(t):\n",
    "                return 0\n",
    "            if s[i]==t[idx]:\n",
    "                idx+=1\n",
    "        return len(t)-idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        i, n = 0, len(s)\n",
    "        for j, c in enumerate(t):\n",
    "            while i < n and s [i] != t[j]: i += 1\n",
    "            if i == n: return len(t) - j\n",
    "            i += 1\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def appendCharacters(self, s: str, t: str) -> int:\n",
    "        cur = 0\n",
    "        n = len(t)\n",
    "        for c in s:\n",
    "            if c == t[cur]:\n",
    "                cur += 1\n",
    "                if cur == n:\n",
    "                    return 0\n",
    "        return n - cur"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
